import random


class TreeNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None


def build_cartesian_tree(arr):
    if not arr:
        return None
    stack = []
    root = None
    for i, (key, value) in enumerate(arr):
        node = TreeNode(key, value)
        last = None
        while stack and stack[-1].value > value:
            last = stack.pop()
        if stack:
            stack[-1].right = node
        else:
            root = node
        node.left = last
        stack.append(node)
    return root


def inorder_traversal(root):
    result = []

    def _inorder(node):
        if node:
            _inorder(node.left)
            result.append((node.key, node.value))
            _inorder(node.right)

    _inorder(root)
    return result


def preorder_traversal(root):
    result = []

    def _preorder(node):
        if node:
            result.append((node.key, node.value))
            _preorder(node.left)
            _preorder(node.right)

    _preorder(root)
    return result


def postorder_traversal(root):
    result = []

    def _postorder(node):
        if node:
            _postorder(node.left)
            _postorder(node.right)
            result.append((node.key, node.value))

    _postorder(root)
    return result


def get_tree_height(root):
    if not root:
        return 0
    left_height = get_tree_height(root.left)
    right_height = get_tree_height(root.right)
    return max(left_height, right_height) + 1


def print_tree(root):
    if not root:
        return
    height = get_tree_height(root)
    width = 2 ** height - 1
    tree_array = [[" " for _ in range(width)] for _ in range(height)]

    def fill_tree_array(node, level, left, right):
        if not node:
            return
        mid = (left + right) // 2
        tree_array[level][mid] = f"({node.key},{node.value})"
        fill_tree_array(node.left, level + 1, left, mid - 1)
        fill_tree_array(node.right, level + 1, mid + 1, right)

    fill_tree_array(root, 0, 0, width - 1)

    for row in tree_array:
        print("".join(row))

# 示例使用
n = 16
arr = [None] * n
for i in range(n):
    arr[i] = (i+1, random.randint(1, 100))
cartesian_tree = build_cartesian_tree(arr)

print("中序遍历结果:", inorder_traversal(cartesian_tree))
print("前序遍历结果:", preorder_traversal(cartesian_tree))
print("后序遍历结果:", postorder_traversal(cartesian_tree))

print("\n笛卡尔树结构:")
print_tree(cartesian_tree)
